#include <string>
#include <cstdlib>
#include <cassert>
#include <vector>
#include <iostream>
#include <optional>
#include <list>
#include <array>
#include <algorithm>

std::size_t hash(const std::string& input);

struct Light
{
    Light(const std::string& input, std::size_t begin, std::size_t end);
    Light() = default;
    
    std::string label;
    std::optional<std::size_t> focalLength;
};

Light::Light(const std::string& input, std::size_t begin, std::size_t end) :
    label{}, focalLength{}
{
    // Find '=' or '-'
    std::size_t splitPos {begin + 1};
    while (true)
    {
        if (splitPos >= input.size())
            assert(false);
        if (input[splitPos] == '=' || input[splitPos] == '-')
            break;
        splitPos += 1;
    }
    
    this->label.assign( std::string{input, begin, splitPos - begin} );
    if (input[splitPos] == '-')
    {
        assert(splitPos + 1 == end);
    }
    else
    {
        std::size_t focalLengthBegin{splitPos + 1};
        this->focalLength = 
            std::optional<std::size_t>{
                std::stoull(input.substr(focalLengthBegin, end - focalLengthBegin))
            };
    }
}

void part2(const std::string& input)
{
    std::vector<Light> lights {};
    std::array< std::list<const Light*>, 256> boxes {};
    
    // Split with ','
    std::size_t begin {0};
    while (begin < input.size())
    {
        if (input[begin] == ',') 
        {
            begin += 1;
            continue;
        }
        // input[begin] is not a ',', find next ',' or end
        std::size_t end {begin + 1};
        while (true)
        {
            if (end >= input.size() || input[end] == ',')
                break;
            end += 1;
        }

        // input[begin, end) is not ','
        lights.emplace_back(input, begin, end);
        begin = end + 1;
    }

    // for (const Light& l : lights)   
    // {
    //     std::cout << l.label;
    //     if (l.focalLength.has_value())
    //         std::cout << " => " << l.focalLength.value();
    //     std::cout << std::endl;
    // }

    auto showBoxex = [&boxes] () {

        for (const auto& box : boxes)
        {
            if (box.empty()) continue;

        }
    };

    for (const Light& l : lights)
    {
        std::size_t boxIndex {hash(l.label)};
        std::list<const Light*>& box {boxes[boxIndex]};

        bool exit {false};
        for (auto iter = box.begin(); iter != box.end(); ++iter)
        {
            const Light* light {*iter};
            if (light->label == l.label)
            {
                exit = true;
                if (l.focalLength.has_value())
                    *iter = &l;
                else
                    box.erase(iter);
                break;
            }
        }

        if (!exit) 
        {
            if (l.focalLength.has_value())
                box.emplace_back(&l);
        }
    }

    std::size_t sum {0};
    for (std::size_t boxIdx = 0; boxIdx < 256; ++boxIdx)
    {
        std::list<const Light*> box {boxes[boxIdx]};
        std::size_t lightIdx = 0;
        for (const Light* l : box)
        {
            sum += (boxIdx + 1) * (lightIdx + 1) * l->focalLength.value();
            lightIdx += 1;
        }
    }

    std::cout << sum << std::endl;
}